1. Field of the Invention
This invention relates to prefetching data and, in particular, to prefetching data based upon previous data accesses.
2. Description of the Related Art
Prefetching data is an important technique used to improve the speed for executing a computer program. The speed of execution can be improved by fetching data from memory before the data is needed for use in a central processing unit.
Several techniques for prefetching data have been developed. These techniques are used to prefetch data that is consecutive in an address space or strided with a constant stride. Some of the techniques particularize the prefetches for sequences of cache misses. Others store certain selected references and the associated data in a buffer and supply the references and the data faster upon reference. These techniques either use differences between references made in a neighborhood or compare addresses with returned data to detect accesses through linked lists. When two records are located at addresses a and b, the address b is stored at a constant offset from the location at address a. Hence, by tracking the constant offset between data returned, when the link in a record is accessed, and the beginning address of that record, chained accesses can be tracked and prefetched.
However, the above techniques of tracking linked accesses cannot be used when accesses are made, not by link addresses, but by array indices stored in other arrays. Thus, when accessing the sequence A[B[I]]. I=1, 2, . . . , the data returned for array B[I] is not an address. Instead, the data returned is an index of Array A and is not related to the previous address by a constant.
Therefore, what are needed are techniques for accessing data by array indices stored in another array.